#ifndef _VECTOR_H_
#define _VECTOR_H_

#include <iostream>

#include "communal.h"
#define DEFAULT_CAPACITY 3

typedef int Rank;

template <typename T>
class Vector {
   public:
    //默认构造函数：容量为c，大小为s，全部初始化为v
    Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0);
    //使用数组整体构造
    Vector(T const* A, Rank n);
    //使用数组区间构造
    Vector(T const* A, Rank lo, Rank hi);
    //使用向量整体拷贝构造
    Vector(Vector<T> const& V);
    //使用向量区间构造
    Vector(Vector<T> const& V, Rank lo, Rank hi);

    ~Vector();

    /****只读访问接口****/
    //返回规模
    Rank size() const;
    //判空
    bool empty() const;
    //返回相邻逆序对儿的个数
    int disordered() const;
    //无序向量整体查找
    Rank find(T const& e) const;
    //无序向量区间查找
    Rank find(T const& e, Rank lo, Rank hi) const;
    //有序向量整体查找
    Rank search(T const& e, SearchMethod m = BIN_SEARCH) const;
    //有序向量区间查找
    Rank search(T const& e, Rank lo, Rank hi, SearchMethod m = BIN_SEARCH) const;

    //重载下标操作符[]
    T& operator[](Rank r) const;
    //重载赋值运算符=，便于直接拷贝，返回引用便于链式赋值
    Vector<T>& operator=(Vector<T> const& V);

    //删除秩为r的元素
    T remove(Rank r);
    //删除秩在[lo,hi)之间的元素
    int remove(Rank lo, Rank hi);
    //插入元素
    Rank insert(Rank r, T const& e);
    //默认作为末尾插入
    Rank insert(T const& e);
    //区间排序
    void sort(Rank lo, Rank hi, SortMethod m = BUBBLE_SORT);
    //整体排序
    void sort(SortMethod m = BUBBLE_SORT);
    //区间置乱
    void unsort(Rank lo, Rank hi);
    //整体置乱
    void unsort();
    //无序向量去重
    int deduplicate();
    //有序向量去重
    int uniquify();

    //使用函数指针遍历
    void traverse(void (*)(T&));
    //使用仿函数（函数对象）遍历
    template <typename VST>
    void traverse(VST&);

   protected:
    Rank _size;
    int _capacity;
    T* _elem;

    //复制数组
    void copyFrom(T const* A, Rank lo, Rank hi);
    //扩容
    void expand();
    //收缩
    void shrink();
    //冒泡排序
    void bubbleSort(Rank lo, Rank hi);
    //插入排序
    void insertionSort(Rank lo, Rank hi);
    //希尔排序
    void shellSort(Rank lo, Rank hi);
    //选取最大值
    Rank max(Rank lo, Rank hi);
    //选择排序
    void selectionSort(Rank lo, Rank hi);
    //堆排序
    void heapSort(Rank lo, Rank hi);
    //归并排序迭代版
    void mergeSort_iteratively(Rank lo, Rank hi);
    //有序子列归并
    void merge(Rank lo, Rank mi, Rank hi);
    //归并排序递归版
    void mergeSort_recursively(Rank lo, Rank hi);
    //轴点构造
    Rank partition(Rank lo, Rank hi);
    //快速排序
    void quickSort(Rank lo, Rank hi);
    //计数排序
    void countingSort(Rank lo, Rank hi);
    //基数排序
    void radixSort(Rank lo, Rank hi);

};  //Vector

/****public****/
template <typename T>
Vector<T>::Vector(int c, int s, T v) {
    _elem = new T[_capacity = c];
    for (_size = 0; _size < s; ++_size) {
        _elem[_size] = v;
    }
}

template <typename T>
Vector<T>::Vector(T const* A, Rank n) {
    copyFrom(A, 0, n);
}

template <typename T>
Vector<T>::Vector(T const* A, Rank lo, Rank hi) {
    copyFrom(A, lo, hi);
}

template <typename T>
Vector<T>::Vector(Vector<T> const& V) {
    copyFrom(V._elem, 0, V._size);
}

template <typename T>
Vector<T>::Vector(Vector<T> const& V, Rank lo, Rank hi) {
    copyFrom(V._elem, lo, hi);
}

template <typename T>
Vector<T>::~Vector() {
    delete[] _elem;
    _elem = nullptr;
}

/****只读访问接口****/
template <typename T>
Rank Vector<T>::size() const {
    return this->_size;
}

template <typename T>
bool Vector<T>::empty() const {
    return !(this->_elem);
}

template <typename T>
int Vector<T>::disordered() const {
    int i = 1;
    int count = 0;
    for (i = 1; i < _size; ++i) {
        if (_elem[i - 1] > _elem[i])
            count++;
    }
    return count;
}

template <typename T>
Rank Vector<T>::find(T const& e) const {
    return find(e, 0, _size);
}

template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const {
    while ((lo < hi--) && e != _elem[hi])
        ;
    return hi;
}

template <typename T>
Rank Vector<T>::search(T const& e, SearchMethod m) const {
    return (_size <= 0) ? -1 : search(e, 0, _size, m);
}

template <typename T>
Rank Vector<T>::search(T const& e, Rank lo, Rank hi, SearchMethod m) const {
    switch (m) {
        case BIN_SEARCH:
            return binSearch(_elem, e, lo, hi);
            break;
        case FIB_SEARCH:
            return fibSearch(_elem, e, lo, hi);
            break;
        default:
            return fibSearch(_elem, e, lo, hi);
            break;
    }
}

template <typename T>
T& Vector<T>::operator[](Rank r) const {
    return _elem[r];
}

template <typename T>
Vector<T>& Vector<T>::operator=(Vector<T> const& V) {
    if (_elem)
        delete[] _elem;
    copyFrom(V._elem, 0, V._size);
    return *this;
}

template <typename T>
T Vector<T>::remove(Rank r) {
    T e = _elem[r];
    remove(r, r + 1);
    return e;
}

template <typename T>
int Vector<T>::remove(Rank lo, Rank hi) {
    if (lo == hi)
        return 0;
    while (hi < _size)
        _elem[lo++] = _elem[hi++];
    _size = lo;
    shrink();
    return hi - lo;
}

template <typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
    expand();
    for (int i = _size; i > r; --i)
        _elem[i] = _elem[i - 1];
    _elem[r] = e;
    _size++;
    return r;
}

template <typename T>
Rank Vector<T>::insert(T const& e) {
    return insert(_size, e);
}

template <typename T>
void Vector<T>::sort(Rank lo, Rank hi, SortMethod m) {
    switch (m) {
        case BUBBLE_SORT:
            bubbleSort(lo, hi);
            break;
        case INSERTION_SORT:
            insertionSort(lo, hi);
            break;
        case SHELL_SORT:
            shellSort(lo, hi);
            break;
        case SELECTION_SORT:
            selectionSort(lo, hi);
            break;
        case HEAP_SORT:
            heapSort(lo, hi);
            break;
        case MERGE_SORT_ITERATIVELY:
            mergeSort_iteratively(lo, hi);
            break;
        case MERGE_SORT_RECURSIVELY:
            mergeSort_recursively(lo, hi);
            break;
        case QUICK_SORT:
            quickSort(lo, hi);
            break;
        case COUNTING_SORT:
            countingSort(lo, hi);
            break;
        case RADIX_SORT:
            radixSort(lo, hi);
            break;
        default:
            quickSort(lo, hi);
            break;
    }
    return;
}

template <typename T>
void Vector<T>::sort(SortMethod m) {
    sort(0, _size, m);
}

template <typename T>
void Vector<T>::unsort(Rank lo, Rank hi) {
    T* V = _elem + lo;
    for (int i = hi - lo; i > 0; --i) {
        swap(V[i - 1], V[rand() % i]);
    }
}

template <typename T>
void Vector<T>::unsort() {
    unsort(0, _size);
}

template <typename T>
int Vector<T>::deduplicate() {
    int oldSize = _size;
    Rank i = 1;
    while (i < _size) {
        (find(_elem[i], 0, i) < 0) ? ++i : remove(i);
    }
    return oldSize - _size;
}

template <typename T>
int Vector<T>::uniquify() {
    Rank i = 0, j = 0;
    while (++j < _size) {
        if (_elem[i] != _elem[j])
            _elem[++i] = _elem[j];
    }
    _size = ++i;
    shrink();
    return j - i;
}

template <typename T>
void Vector<T>::traverse(void (*visit)(T&)) {
    for (int i = 0; i < _size; ++i) {
        visit(_elem[i]);
    }
    return;
}

template <typename T>
template <typename VST>
void Vector<T>::traverse(VST& visit) {
    for (int i = 0; i < _size; ++i) {
        visit(_elem[i]);
    }
    return;
}

/*****protected****/
template <typename T>
void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi) {
    _elem = new T[_capacity = (hi - lo) * 2];
    _size = 0;
    while (lo < hi) {
        _elem[_size++] = A[lo++];
    }
    return;
}

template <typename T>
void Vector<T>::expand() {
    if (_size < _capacity)
        return;
    if (_capacity < DEFAULT_CAPACITY)
        _capacity = DEFAULT_CAPACITY;
    T* oldElem = _elem;
    _elem = new T[_capacity <<= 1];
    for (int i = 0; i < _size; ++i)
        _elem[i] = oldElem[i];
    delete[] oldElem;
    return;
}

template <typename T>
void Vector<T>::shrink() {
    if (_capacity < DEFAULT_CAPACITY << 1)
        return;
    if (_size << 2 > _capacity)
        return;
    T* oldElem = _elem;
    _elem = new T[_capacity >>= 1];
    for (int i = 0; i < _size; ++i)
        _elem[i] = oldElem[i];
    delete[] oldElem;
    return;
}

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi) {
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (int i = lo + 1; i < hi; ++i) {
            if (_elem[i - 1] > _elem[i]) {
                swap(_elem[i - 1], _elem[i]);
                sorted = false;
            }
        }
        hi--;
    }
    return;
}

template <typename T>
void Vector<T>::insertionSort(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
void Vector<T>::shellSort(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
Rank Vector<T>::max(Rank lo, Rank hi) {
    //TODO
    return 0;
}

template <typename T>
void Vector<T>::selectionSort(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
void Vector<T>::heapSort(Rank lo, Rank hi) {
    return;
}
template <typename T>
void Vector<T>::mergeSort_iteratively(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {
    Rank i = 0, j = 0, k = 0;
    T* A = _elem + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    for (i = 0; i < lb; ++i)
        B[i] = A[i];

    T* C = _elem + mi;
    int lc = hi - mi;

    for (i = 0, j = 0, k = 0; (j < lb) || (k < lc);) {
        if ((j < lb) && (!(k < lc) || B[j] <= C[k]))
            A[i++] = B[j++];
        if ((k < lc) && (!(j < lb) || C[k] < B[j]))
            A[i++] = C[k++];
    }
    delete[] B;
    return;
}

template <typename T>
void Vector<T>::mergeSort_recursively(Rank lo, Rank hi) {
    if (hi - lo < 2)
        return;
    int mi = (lo + hi) / 2;
    mergeSort_iteratively(lo, mi);
    mergeSort_recursively(mi, hi);
    merge(lo, mi, hi);
    return;
}

template <typename T>
Rank Vector<T>::partition(Rank lo, Rank hi) {
    //TODO
    return 0;
}

template <typename T>
void Vector<T>::quickSort(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
void Vector<T>::countingSort(Rank lo, Rank hi) {
    //TODO
    return;
}

template <typename T>
void Vector<T>::radixSort(Rank lo, Rank hi) {
    //TODO
    return;
}

#endif